package com.leetcode;

public class L0035 {
    public static void main(String[] args) {
        int[] arr={1,3};
        int target=0;
        int n=searchInsert(arr,target);
        System.out.println(n);
    }
    public static int searchInsert(int[] nums, int target) {
        return Dichotomy(nums,0,nums.length-1,target);
    }
    public static int Dichotomy(int[] nums,int left,int right,int target){
        int mid=(left+right)/2;
        if (left>=right){
            if(target>nums[left])
                return left+1;
            else
                return left;
        }
        if (nums[mid]==target)
            return mid;
        else if (nums[mid]<target)
            return Dichotomy(nums,mid+1,nums.length-1,target);
        else
            return Dichotomy(nums,left,mid-1,target);
    }
}
